Cache memories are used as small high speed buffer memories between a processor and a main memory. They may be used to hold the most active portion of a main memory in order to improve access times for those contents of the memory which are most frequently used by the processor.
Known cache memories generally fall into one of three types. They may be fully associative, set associative or direct mapped. Fully associative cache memories may consist of a content addressable memory (CAM) and a data RAM. Content addressable memories (CAMs) consist of rows and columns of memory cells generally similar to RAM cells providing read and write functions but additional circuitry is provided to permit association. The CAM cells are used to hold memory addresses and during an association operation an input to the CAM represents a memory address and the CAM compares the input with the addresses held in the CAM to see whether or not a match occurs and when a match is found an output signal is provided to a corresponding location in the data RAM so that a read or write operation may take place with the corresponding location in the data RAM of the cache. The cells of the CAM are arranged so that each row of cells holds a memory address and that row of cells is connected by a match line to a corresponding word line of the data RAM to enable access of the data RAM in that word line when a match occurs on that match line. In a fully associative cache each row of the CAM holds the full address of a corresponding main memory location and the inputs to the CAM require the full address to be input.
In a direct mapped cache the address of each main memory location used in the cache is divided into a first part represented by the most significant bits, usually referred to as the page address, and a second part represented by the least significant bits and usually referred to as the line in page address. A RAM (called a Tag RAM) is used to hold a plurality of page addresses of memory locations in the main memory. Data is held in a data RAM as already described. However the input to the Tag RAM and the data RAM uses only the line in page part of the memory addresses. The Tag RAM is accessed at the location identified by the line in page address and the RAM outputs to a comparator the stored page address from that RAM location. The most significant bits of the main memory address are fed directly to the comparator to see whether or not they agree with the corresponding most significant bits of the address output by the RAM. If they agree then a cache hit is obtained and data is output from the location of the data RAM accessed by the line in page input. If no agreement is found by the comparator then access to the data RAM is prevented.
In a set associative cache a plurality of Tag RAMs are used in parallel and the least significant bits of each input address are used to address each of the Tag RAMs in parallel as well as associated data RAMs. The page address held in the addressed row of each Tag RAM is output and compared in a comparator with the most significant bits of the main memory address which are fed directly to the comparator similar to the process already described for a direct mapped cache. If the output of one of the Tag RAMs is found to agree on comparison of the most significant address bits with the main memory address then the corresponding word line of the data RAM associated with that Tag RAM is accessed.
It will therefore be understood that it is only in a fully associative cache that all bits of the memory location address are required as an initial input in order to determine whether the cache contains data corresponding to that memory location. The other types of cache only require as an initial input some of the bits of the memory location address.
In many applications it is desirable to use virtual memory addressing whereby a process executes instructions referring to virtual memory locations. Conveniently virtual addresses are defined as a virtual page address together with a line or word in page address. Commonly the line or word in page address may be the same for both physical and virtual addresses and the virtual aspect of the addressing is dealt with solely in the virtual page address. Conveniently the page addresses may be dealt with by the most significant bits of an address and the line or word in page address may be indicated by the least significant bits of the address. When executing a process using virtual addresses it is necessary to translate the virtual page address into a physical page address corresponding to an actual physical location in the main memory. If virtual addressing is to be used with a cache memory it will be understood that a fully associative cache would normally require translation of the virtual page address into a physical page address before the full address to be searched by the CAM could be input to the CAM. The translation of virtual page addresses to physical page addresses may be carried out by a translation lookaside buffer (TLB). To require the use of such a TLB to form a physical page address from a virtual page address before inputting an address to a fully associative cache does of course introduce additional delay and reduce the value of using a cache memory. For this reason caches using virtual addressing have usually been formed as a direct mapped or set associative cache. In this way the input address to the Tag RAMs and data RAMs has constituted the line or word in page address which does not require translation to a physical address. The most significant bits of the virtual address forming the virtual page address are not used in the initial input to the RAMs but have been fed through a TLB to form a physical page address in parallel with the addressing operation of the RAMs by the line in page input to the RAMs. If a valid entry is found in one of the RAMs for the line in page address then the page address representing the physical address of the corresponding main memory location is output from the RAM to a comparator where the most significant bits of that address may be compared with the output of the TLB now representing the physical page address determined by the address translation operation. As the RAM accessing operation and the translation from virtual to physical page address are both carried out in parallel there is no additional delay of the type which has been necessary if virtual memory addressing is used with a fully associative cache.
It is an object of the present invention to provide an improved cache which permits virtual addressing without the additional delay of requiring address translation prior to searching the cache for a corresponding entry.